Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • The curious case of the circle
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

Definition 1 (Directed Hausdorff Distance) For two subsets compact X,Y\subset\mathbb R^n, their directed Hausdorff distance is \vec{d}_H(X,Y)=\inf\big\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\big\}.

All metric properties but symmetry.

Definition 2 (Hausdorff Distance)  

\begin{aligned} d_H(X,Y) &=\max\big\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\big\} \\ &=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}. \end{aligned}

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let (Z,d) be a metric space and X, Y\subset Z compact subsets. d^Z_H(X,Y)=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}.

d_H(X, Y)=0 if and only if X=Y.

Z=S^1 is the circle with circumference 2\pi

d_H(X,S^1)=\frac{\pi}{4}.

What if the subsets X,Y have no common embeddding?

Isometric embedding

Definition 4 (The Gromov–Hausdorff Distance) For two abstract metric spaces (X,d_X) and (Y,d_Y), define d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y))

An Example

Some Properties and Results

  • d_{GH}(X,Y)=0 if and only if X, Y are isometric

  • \tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}

  • When X, Y are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If X,Y metric trees, then NP-hard (Aggarwal et al.)

  • If X,Y\subset\mathbb{R}^1, then \frac{5}{4}-approximable (Majhi et al.)

  1. Let (Z,d) be a metric space and X,Y\subset Z
    • d^Z_H(X,Y) is well-defined
  2. (X,d) and (Y,d) are also metric spaces
    • d_{GH}(X,Y) can also be defined

How the two distances d^Z_H(X,Z) and d_{GH}(X,Y) compare?

  • d_{GH}(X,Y)\color{green}{\leq} d_H(X,Y)
    • Z is just one ambient of X,Y!
  • d_{GH}(X,Y) \color{red}{=} d_H(X,Y)?

The Circle and A Subset

  • Let Z be the circle with circumference 2\pi
  • X be a singleton subset, Y=Z
  • \color{green}{d_H(X,S^1)}=\color{red}{d_{GH}(X,S^1)}=\frac{\pi}{2}
  • \frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2}

The Circle and A Subset

  • \color{green}{d_H(X,S^1)}=\frac{\pi}{4}
  • \frac{1}{2}0\leq \color{red}{d_{GH}(X,S^1)}\leq \frac{1}{2}\pi \implies ?
  • One can show that d_{GH}(X,S^1)=d_H(X,S^1)

The Curious Case of the Circle

\frac{\pi}{3}=\color{red}{d_{GH}(X,S^1)}<\color{green}{d_{H}(X,S^1)}=\frac{\pi}{3}+\varepsilon.

Density is The Key

Theorem 1 (DCG 2023) For X\subset S^1 with d_H(X,S^1)<\color{red}{\frac{\pi}{6}}, then d_{GH}(X,S^1)=d_H(X,S^1).

  • Proof is topological (Vietoris–Rips complex, Nerve Lemma)
  • Is \frac{\pi}{6} optimal?

Theorem 2 (2024) For X\subset S^1 with d_H(X,S^1)<\color{green}{\frac{\pi}{3}}, then d_{GH}(X,S^1)=d_H(X,S^1).

  • Proof is purely geometric

Another Perspective: Lower Bound

Corollary 1 (One Subset) Restating Theorem 2, we get d_{GH}(X,S^1)\geq\min\big\{d_H(X, S^1),\tfrac{\pi}{3}\big\}.

Corollary 2 (Two Subsets) For X,Y\subset S^1 with d_H(Y,S^1)\leq\varepsilon, then d_{GH}(X,Y)\geq\min\big\{d_H(X, Y)-2\varepsilon,\tfrac{\pi}{3}-\varepsilon\big\}.

  • O(n^2) lower-bound for \max\big\{|X|, |Y|\big\}=n.

Intuition: when a sample X\subset Z becomes dense enough, it starts to capture the geometry of the space.

Generally: d_{GH}(X,Z)\geq\min\big\{\color{green}{C}\cdot d_H(X, Z), \color{red}{D}\big\}?

  • Cirlce: When Z=S^1, then \color{green}{C}=1 and \color{red}{D}=\frac{\pi}{3}.
    • Both are optimal constants

Theorem 3 (Bad News) For any \color{green}{C}>0, there exists a compact metric space Z and a dense subset X\subseteq Z with d_{GH}(X,Z) < \green{C}\ d_{H}(X,Z).

Good News

Theorem 4 (Closed Riemannian Manifolds) For X\subset M, we have d_{GH}(X,M)\geq\min\bigg\{\color{green}{\frac{1}{2}}d_H(X, S^1),\color{green}{\frac{\rho}{6}}\bigg\}.

  • \rho is the convexity radius of M
  • C=\frac{1}{2} can be improved using Jung’s theorem

Metric Trees and Graphs

Theorem 5 (Trees) Let T be a compact tree with finite edges. For any X\subset T so that d_H(T,X)<\vec{d}_H(\delta T, X), we have d_{GH}(X,T)=d_H(X, T).

Theorem 6 (Graphs) Let G be a compact tree with finite edges. For any X\subset G so that d_H(G,X)<\vec{d}_H(\delta G, X), we have d_{GH}(X,G)\geq\min\bigg\{{d_H(X, S^1),\tfrac{e(G)}{12}}\bigg\}.

  • e(G) denotes the length of the shortest edge.

Questions

  • For metric graphs, is the density constant \frac{e(G)}{12} optimal?

    • We conjecture that \frac{e(G)}{8} should suffice.

  • What about Riemannian manifolds with bounday?

  • Are there classes of metric spaces—like the circle, metric graphs—so that C=1?

Thank you